package com.example.leetcode.problem.isuniquelcci;

import org.springframework.util.Assert;

public class CompressStringLcci {

    /**
     * 面试题 01.06. 字符串压缩
     * 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
     * 比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
     * 你可以假设字符串中只包含大小写英文字母（a至z）。
     * <p>
     * 示例1:
     * <p>
     * 输入："aabcccccaaa"
     * 输出："a2b1c5a3"
     * 示例2:
     * <p>
     * 输入："abbccd"
     * 输出："abbccd"
     * 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
     * 提示：
     * <p>
     * 字符串长度在[0, 50000]范围内。
     *
     * @param args
     */
    public static void main(String[] args) {
        CompressStringLcci test = new CompressStringLcci();
        String input = "aabcccccaaa";
        String output = "a2b1c5a3";
        Assert.isTrue(test.compressString(input).equals(output));
        input = "abbccd";
        output = "abbccd";
        Assert.isTrue(test.compressString(input).equals(output));
    }

    /**
     * 方法一：模拟
     * 思路
     * <p>
     * 字符串压缩的方式就是将连续出现的相同字符按照 字符 + 出现次数 压缩。如果压缩后的字符串长度变短，则返回压缩后的字符串，否则保留原来的字符串，所以我们模拟这个过程构建字符串即可。
     * <p>
     * 算法
     * <p>
     * 我们从左往右遍历字符串，用 chch 记录当前要压缩的字符，\textit{cnt}cnt 记录 chch 出现的次数，如果当前枚举到的字符 s[i]s[i] 等于 chch ，我们就更新 \textit{cnt}cnt 的计数，即 cnt = cnt + 1，否则我们按题目要求将 chch 以及 \textit{cnt}cnt 更新到答案字符串 \textit{ans}ans 里，即 ans = ans + ch + cnt，完成对 chch 字符的压缩。随后更新 chch 为 s[i]s[i]，cntcnt 为 11，表示将压缩的字符更改为 s[i]s[i]。
     * <p>
     * 在遍历结束之后，我们就得到了压缩后的字符串 \textit{ans}ans，并将其长度与原串长度进行比较。如果长度没有变短，则返回原串，否则返回压缩后的字符串。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n)O(n)，其中 nn 为字符串的长度，即遍历一次字符串的复杂度。
     * 空间复杂度：O(1)O(1)，只需要常数空间（不包括存储答案 \textit{ans}ans 的空间）存储变量。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/compress-string-lcci/solution/zi-fu-chuan-ya-suo-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/compress-string-lcci/solution/zi-fu-chuan-ya-suo-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param S
     * @return
     */
    public String compressString(String S) {
        // 空串处理
        if (S.length() == 0) {
            return S;
        }
        StringBuffer ans = new StringBuffer();
        int cnt = 1;
        char ch = S.charAt(0);
        for (int i = 1; i < S.length(); ++i) {
            if (ch == S.charAt(i)) {
                cnt++;
            } else {
                ans.append(ch);
                ans.append(cnt);
                ch = S.charAt(i);
                cnt = 1;
            }
        }
        ans.append(ch);
        ans.append(cnt);
        return ans.length() >= S.length() ? S : ans.toString();
    }

}
